Expression add operators

Time: O(4^N); Space: O(N); hard

Given a string that contains only digits 0-9 and a target value,

return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Example 1:

Input: num = “123”, target = 6

Output: [“1+2+3”, “1*2*3”]

Example 2:

Input: num = “232”, target = 8

Output: [“2*3+2”, “2+3*2”]

Example 3:

Input: num = “105”, target = 5

Output: [“1*0+5”,“10-5”]

Example 4:

Input: num = “00”, target = 0

Output: [“0+0”, “0-0”, “0*0”]

Example 5:

Input: num = “3456237490”, target = 9191

Output: []

Hints:

  1. Note that a number can contain multiple digits.

  2. Since the question asks us to find all of the valid expressions, we need a way to iterate over all of them. (Hint: Recursion!)

  3. We can keep track of the expression string and evaluate it at the very end. But that would take a lot of time. Can we keep track of the expression’s value as well so as to avoid the evaluation at the very end of recursion?

  4. Think carefully about the multiply operator. It has a higher precedence than the addition and subtraction operators.

    • 1 + 2 = 3

    • 1 + 2 - 4 –> 3 - 4 –> -1

    • 1 + 2 - 4 * 12 –> -1 * 12 –> -12 (WRONG!)

    • 1 + 2 - 4 * 12 –> -1 - (-4) + (-4 * 12) –> 3 + (-48) –> -45 (CORRECT!)

  5. We simply need to keep track of the last operand in our expression and reverse it’s effect on the expression’s value while considering the multiply operator.

[1]:

class Solution1(object):
    """
    Time: O(4^N)
    Space: O(N)
    """
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        result, expr = [], []
        val, i = 0, 0
        val_str = ''
        while i < len(num):
            val = val * 10 + ord(num[i]) - ord('0')
            val_str += num[i]
            # Avoid "00...".
            if str(val) != val_str:
                break
            expr.append(val_str)
            self.addOperatorsDFS(num, target, i + 1, 0, val, expr, result)
            expr.pop()
            i += 1
        return result

    def addOperatorsDFS(self, num, target, pos, operand1, operand2, expr, result):
        if pos == len(num) and operand1 + operand2 == target:
            result.append(''.join(expr))
        else:
            val, i = 0, pos
            val_str = ''
            while i < len(num):
                val = val * 10 + ord(num[i]) - ord('0')
                val_str += num[i]
                # Avoid "00...".
                if str(val) != val_str:
                    break

                # Case '+':
                expr.append("+" + val_str)
                self.addOperatorsDFS(num, target, i + 1, operand1 + operand2, val, expr, result)
                expr.pop()

                # Case '-':
                expr.append("-" + val_str)
                self.addOperatorsDFS(num, target, i + 1, operand1 + operand2, -val, expr, result)
                expr.pop()

                # Case '*':
                expr.append("*" + val_str)
                self.addOperatorsDFS(num, target, i + 1, operand1, operand2 * val, expr, result)
                expr.pop()

                i += 1

[8]:

s = Solution1()

num = "123"
target = 6
assert s.addOperators(num, target) == ["1+2+3", "1*2*3"]

num = "232"
target = 8
assert s.addOperators(num, target) == ["2*3+2", "2+3*2"] or ['2+3*2', '2*3+2']

num = "105"
target = 5
assert s.addOperators(num, target) == ["1*0+5","10-5"] or ["10-5", "1*0+5"]

num = "00"
target = 0
assert s.addOperators(num, target) == ["0+0", "0-0", "0*0"]

num = "3456237490"
target = 9191
assert s.addOperators(num, target) == []